#coding=utf-8


#并查集
# class UnionFindSet():
#     def __init__(self, data_list):
#         """初始化两个字典，一个保存节点的父节点，另外一个保存父节点的大小
#         初始化的时候，将节点的父节点设为自身，size设为1"""
#         self.father_dict = {}
#         self.size_dict = {}
#
#         for node in data_list:
#             self.father_dict[node] = node
#             self.size_dict[node] = 1
#
#     def find(self,node):
#         father = self.father_dict[node]
#         if (node != father):
#             if father != self.father_dict[father]:
#                 self.size_dict[father] -= 1
#             father = self.find(father)
#         self.father_dict[node] = father
#         return father
#
#     def is_same_set(self, node_a, node_b):
#         """查看两个节点是不是在一个集合里面"""
#         return self.find(node_a) == self.find(node_b)
#
#     def union(self, node_a , node_b):
#         """将两个集合合并在一起"""
#         if node_a is None or node_b is None:
#             return
#
#         a_head = self.find(node_a)
#         b_head = self.find(node_b)
#
#         if (a_head != b_head):
#             a_set_size = self.size_dict[a_head]
#             b_set_size = self.size_dict[b_head]
#             if (a_set_size >= b_set_size):
#                 self.father_dict[b_head] = a_head
#                 self.size_dict[a_head] = a_set_size + b_set_size
#             else:
#                 self.father_dict[a_head] = b_head
#                 self.size_dict[b_head] = a_set_size + b_set_size




#最短路径问题
##Floyd算法
# def Floyd(n):
#     global dis
#     for k in range(n): #中转点
#         for v in range(n): #起点
#             for w in range(n): #终点
#                 dis[v][w] = min(dis[v][w] , dis[v][k] + dis[k][w])
#
# N,M,Q = map(int,input().split())
# dis = [[float('inf') for i in range(N)] for j in range(N)]
# for i in range(N):
#     dis[i][i] = 0
# for i in range(M):
#     u,v,w = map(int,input().split())
#     dis[u-1][v-1] = min(dis[u-1][v-1] , w)
#     dis[v-1][u-1] = dis[u-1][v-1]
# Floyd(N)
# for i in range(Q):
#     u , v = map(int,input().split())
#     d = dis[u-1][v-1]
#     if d == float('inf'):
#         print(-1)
#     else:
#         print(d)

#Dijkstra
# N, M = map(int, input().split())
# cost = [[float('inf') for j in range(N)] for i in range(N)]
# for i in range(M):
#     s, e, v = map(int, input().split())
#     cost[s - 1][e - 1] = cost[e - 1][s - 1] = v
# flag = [False for i in range(N)]
# d = [float('inf') for i in range(N)]
# d[0] = 0
# while True:
#     u = -1
#     for i in range(N):
#         if (flag[i] == False) and (u == -1 or d[u] > d[i]):
#             u = i
#     if u == -1:
#         break
#     flag[u] = True
#     for i in range(N):
#         d[i] = min(d[i], d[u] + cost[u][i])
#
# for i in range(N):
#     print(-1, end=" ") if d[i] == float('inf') else print(d[i], end=" ")

#prim
# N , M = map(int,input().split())
# cost = [[float("inf") for i in range(N)] for j in range(N)]
# for i in range(M):
#     u , v , w = map(int,input().split())
#     cost[u-1][v-1] = cost[v-1][u-1] = w
# flag = [False for i in range(N)]
# d = [float('inf') for i in range(N)]
# d[0] = 0
# ans = 0
# while True:
#     u = -1
#     for i in range(N):
#         if (flag[i] == False) and (u == -1 or d[u] > d[i]):
#             u = i
#     if u == -1:
#         break
#     ans += d[u]
#     flag[u] = True
#     for i in range(N):
#         d[i] = min(d[i],cost[u][i])
#
# print(-1) if ans == float('inf') else print(ans)

# def permutation(A:str)->list:
#     lenstr = len(A)
#     if lenstr <= 1:
#         return [A]
#     else:
#         res = []
#         for i in range(lenstr):
#             ch = A[i]
#             temp = A[0:i] + A[i+1:]
#             for j in permutation(temp):
#                 res.append(ch + j)
#         return res


if __name__ == '__main__':
    a = {'a':1,'b':2}





